#include <stdio.h>

void shell(int stor1[], int n);
void dior(int *r, int x);

// dior
// 为直接插入排序函数，传入参数后将传入的数组从第二个到最后一个由小到大排序。（传入的数组第一个为数字0作为监视哨），此函数测试没问题
// insert_sort
void dior(int *r, int x)
{
    for(int idx = 1; idx < x; idx ++){
        int i = idx - 1;
        int tmp = *(r + idx);
        while(*(r + i) > tmp){
            i --;
        }
        for(int j = idx; j > i + 1; j --){
            *(r + j) = *(r + j - 1);
        }
        *(r + i + 1) = tmp;
    }
}
// 这里是想通过一个写一个希尔排序函数，调用dior函数来简化直接排序，我检查了几遍修改了一下，但还是运行不了，不知道问题出在哪儿了。
void shell(int stor1[], int n)
{
    int k = n; //  n是数组里面数字的数量，先开始将n传给k，然后利用while来实现步长递减，每次步长除以2；
    while (k > 1)
    {
        // 进入while循环后，将n除以2得到分组的数量，利用for循环将每组数字取出——调用dior函数排序——写回去；
        k /= 2; // 然后进行下一次步长循环，最终k等于1结束循环，传进shell的参数实现排序。
        for (int i = 0; i < k; i++)
        {
            int storf[13] = {
                0,
            }; // 创建一个临时数组，将要排序的数放进去调用dior函数，完了再写回去
            int s = 1, u = 1;
            int valid_number = 0;
            for (int ct = 1; ct <= n / k; ct++)
            {
                if(u + i < n){
                    storf[s] = stor1[u + i];
                    s++;
                    u += k;
                    valid_number ++;
                }
            }
            int *pt;
            pt = storf;
            dior(pt, valid_number+1);
            int ct1;
            s = 1;
            u = 1;
            for (ct1 = 1; ct1 <= valid_number; ct1++)
            {

                stor1[u + i] = storf[s];
                s++;
                u += k;
            }
        }
    }
}
// 在主函数里面创建一个数组，对数组里面的数字从小到大排序（0除外），这里想的是直接通过调用一次shell函数就实现。
int main(void)
{
    int stor[] = {
        -255,
        69,
        136,
        12,
        135,
        50
    };
    printf("The number u have inputed is:\n"); // 输出一下好做排序结果对比
    int cnt = 0;
    for (cnt = 0; cnt < sizeof stor / sizeof stor[1]; cnt++)
    {
        printf("%d  ", stor[cnt]);
    }
    int store_number = sizeof(stor) / sizeof(stor[0]);
    shell(stor, store_number);

    printf("\n"); // 实现后进行输出
    for (int s = 0; s < store_number; s++)
    {
        printf("%d  ", stor[s]);
    }
    return 0;
}